1. Technical Field
The present invention relates to a method and system for data processing in general, and in particular to a method and system for avoiding livelocks within a computer system. Still more particularly, the present invention relates to a method and system for avoiding protocol livelocks due to stale exclusive/modified directory entries within a non-uniform memory access computer system.
2. Description of the Prior Art
It is well-known in the computer arts that greater computer system performance can be achieved by combining the processing power of several individual processors to form a multiprocessor (MP) computer system. MP computer systems can be designed with a number of different topologies, depending on the performance requirements of a particular application. A symmetric multiprocessor (SMP) configuration, for example, is one of the simpler MP computer system topologies that are commonly used, in which resources such as a system memory are shared by multiple processors. The topology name "symmetric" stems from the fact that all processors within an SMP computer system have symmetric access to all resources within the system.
Although the SMP topology permits the use of relatively simple inter-processor communication and data sharing protocols, the SMP topology overall has a limited scalability and bandwidth, especially at the system memory level as the system scale increases. As a result, another MP computer system topology known as non-uniform memory access (NUMA) has emerged as an alternative design that addresses many of the limitations of the SMP topology, at the expense of some additional complexity.
A typical NUMA computer system includes a number of interconnected nodes. Each node includes at least one processor and a local "system" memory. The NUMA topology name stems from the fact that a processor has lower access latency with respect to data stored in the system memory at its local node than with respect to data stored in the system memory at a remote node. NUMA computer systems can be further classified as either non-cache coherent or cache coherent, depending on whether or not data coherency is maintained among caches in different nodes. The NUMA topology addresses the scalability limitations of the conventional SMP topology by implementing each node within a NUMA computer system as a smaller SMP system. Thus, the shared components within each node can be optimized for use by only a few processors, while the overall system benefits from the availability of larger scale parallelism with relatively low latency.
Despite all the various advantages, a NUMA system also has its fair share of problems, one of them being livelocks. For example, if a reading processor did not modify a cache line that was exclusive to the reading processor and instead cast out the cache line without informing a cache coherency directory, the cache coherency directory would still indicate that the reading processor has the cache line exclusively. Subsequent accesses to the cache line will be forwarded to the reading processor, which will indicate that the reading processor no longer has the cache line. A livelock can occur if a processor from a node different from the node that previously owned the cache line attempts to access the cache line at the same time the reading processor attempts to access the same cache line again. Consequently, it would be desirable to provide a method for avoiding protocol livelocks due to stale exclusive/modified directory entries within a NUMA computer system.